#include <iostream>
#include<unordered_map>
using namespace std;
class Node
{
public:
    int key;
    int value;
    Node* prev;
    Node* next;
    Node(int k = 0, int v = 0):key(k),value(v){}
};


class LRUCache {
private:
    int capacity;
    Node* head;
    unordered_map<int, Node*> hash;

    void remove(Node* x)
    {
        x->prev->next = x->next;
        x->next->prev = x->prev;
    }

    void push_front(Node* x)
    {

        //head为哑节点
        Node* next = head->next;
        x->next = next;
        next->prev = x;
        head->next = x;
        x->prev = head;
    }

    Node* get_node(int key)
    {
        if(!hash.count(key)) return nullptr;
        Node* node = hash[key];
        remove(node);
        push_front(node);
        return node;
    }

public:
    LRUCache(int capacity): capacity(capacity), head(new Node()){
        head->prev = head;
        head->next = head;
    }

    int get(int key) {
        Node* node = get_node(key);
        return node ? node->value : -1;
    }

    void put(int key, int value) {
        Node* node = get_node(key);
        if(node)
        {
            node->value = value;
            return;
        }

        hash[key] = node = new Node(key, value);
        push_front(node);
        if(hash.size() > capacity)
        {
            Node* back_node = head->prev;
            hash.erase(back_node->key);
            remove(back_node);
            delete back_node;
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */


class Solution2 {
public:
    vector<vector<string>> ret;
    vector<string> path;
    vector<vector<string>> solveNQueens(int n) {
        for(int i = 0; i < n; i++)
        {
            path.push_back(string(n, '.'));
        }
        dfs(n, 0);
        return ret;
    }

    void dfs(int n, int pos)
    {
        if(pos == n)
        {
            ret.push_back(path);
            return;
        }
        for(int i = 0; i < n; i++)
        {
            if(check(pos, i, n))
            {
                path[pos][i] = 'Q';
                dfs(n, pos+1);
                path[pos][i] = '.';

            }

        }
    }

    bool check(int row, int col, int n)
    {
        for(int i = row; i >= 0; i--)
        {
            if(path[i][col] == 'Q')
                return false;
        }

        for(int i = row-1, j = col -1; i >= 0 && j >= 0; i--, j--)
        {
            if(path[i][j] == 'Q')
                return false;
        }

        for(int i = row-1, j = col + 1; i >= 0 && j < n; i--, j++)
        {
            if(path[i][j] == 'Q')
                return false;
        }

        return true;
    }
};